`
https://leetcode.cn/problems/kth-largest-element-in-an-array
`

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
  const len = nums.length
  const targetIndex = len - k

  let left = 0, right = len - 1
  let pivotIndex;

  while ((pivotIndex = partition(nums, left, right)) !== targetIndex) {
    if (pivotIndex < targetIndex) {
      left = pivotIndex + 1
    } else {
      right = pivotIndex - 1
    }
  }

  return nums[pivotIndex]
};

// 直接复制双路快排的切分代码
function partition(nums, left, right) {
  // 选择区间里的随机元素作为基准
  const randomIndex = getRandomInt(left, right);
  [nums[left], nums[randomIndex]] = [nums[randomIndex], nums[left]];

  const pivot = nums[left];

  let le = left + 1; // le: less equals
  let ge = right; // ge: greater equals
  // all in nums[left + 1 ... le) <= pivot
  // all in nums(ge ... right] >= pivot
  while (true) {
    while (le <= ge && nums[le] < pivot) {
      le++;
    }
    while (le <= ge && nums[ge] > pivot) {
      ge--;
    }
    // le 来到了第一个大于等于 pivot 的位置
    // ge 来到了第一个小于等于 pivot 的位置

    if (le >= ge) {
      break;
    }
    // 交换 nums[le] 和 nums[ge]
    [nums[le], nums[ge]] = [nums[ge], nums[le]];
    le++;
    ge--;
  }

  // 交换 nums[left] 和 nums[ge]
  [nums[left], nums[ge]] = [nums[ge], nums[left]];
  return ge;
}

// 返回 [min, max] 之间的随机整数
function getRandomInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}